package com.hardy.leetcode;

/**调整搜索二叉树的两个错误节点的位置，不改变搜索二叉树的结构
 * Created by 1340760685@qq.com on 2016/9/28.
 */
public class RecoverBinarySearchTree {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
            left=null;
            right=null;
        }
    }
    public static void recoverTree(TreeNode root) {
        TreeNode[] s1=new TreeNode[1];
        TreeNode[] s2=new TreeNode[1];
        TreeNode[] pre=new TreeNode[1];
        _recoverTree(root,s1,s2,pre);
        int temp=s1[0].val;
        s1[0].val=s2[0].val;
        s2[0].val=temp;
    }

    private static void _recoverTree(TreeNode root, TreeNode[] s1, TreeNode[] s2, TreeNode[] pre) {
        if(root==null){
            return;
        }
        _recoverTree(root.left,s1,s2,pre);
        if(pre[0]!=null&&pre[0].val>root.val){
            if(s1[0]==null){
                s1[0]=pre[0];
                s2[0]=root;
            }else{
                s2[0]=root;
            }
        }
        pre[0]=root;
        _recoverTree(root.right,s1,s2,pre);
    }
}
